/*************************************************************************
	> File Name: Leetcode295.数据流的中位数.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 五  9/24 17:34:09 2021
 ************************************************************************/

//使用大小堆维护中位数
//时间复杂度：
// - addNum: O(logn)
// - findMedian: O(1)
//空间复杂度：O(n)


class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> queMin;  //大根堆
    priority_queue<int, vector<int>, greater<int>> queMax; //小根堆

    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        if (queMin.empty() || num <= queMin.top()) { //要添加的数小于等于中位数
            queMin.push(num);
            if (queMax.size() + 1 < queMin.size()) { //queMin中的数量比queMax中的数量多2个
                queMax.push(queMin.top());
                queMin.pop();
            }
        } else {
            queMax.push(num);
            if (queMax.size() > queMin.size()) {//保证queMax中的数量不大于queMin中的数量
                queMin.push(queMax.top());
                queMax.pop();
            }
        }
    }

    double findMedian() {
        if (queMin.size() > queMax.size()) { //添加的数的总个数为奇数
            return queMin.top();
        }
        return (queMin.top() + queMax.top()) / 2.0;//添加的数的总个数为偶数
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */
